from copy import deepcopy


class Solution:
    def trapRainWater(self, heightMap: list) -> int:
        if not heightMap:
            return 0
        self.length, self.height = len(heightMap[0]), len(heightMap)
        if self.length <= 2 or self.height <= 2:
            return 0
        self.heightMap = heightMap
        self.mid_mat = []
        for i in range(self.height):
            self.mid_mat.append(self.trap(heightMap[i]))
        for j in range(self.length):
            mid_line = self.trap([k[j] for k in heightMap])
            for i in range(self.height):
                self.mid_mat[i][j] = min(self.mid_mat[i][j], mid_line[i])
        # 对于每一谭水,取最小值
        # final_mat = deepcopy(self.mid_mat)
        for i in range(self.height):
            for j in range(self.length):
                if self.mid_mat[i][j] != 0:
                    self.mid_set = set()
                    min_high = self.find_min(i, j)
                    self.mid_mat[i][j] = max(min_high - self.heightMap[i][j], 0)
        return sum(sum(i) for i in self.mid_mat)

    def trap(self, height) -> list:
        length = len(height)
        i, j = 0, length - 1
        res = [0] * length
        max_side = min(height[i], height[j])
        while True:
            directin = (height[i] < height[j])
            if directin:
                i += 1
                if height[i] < max_side:
                    res[i] = (max_side - height[i])
                else:
                    max_side = min(height[i], height[j])
            else:
                j -= 1
                if height[j] < max_side:
                    res[j] += (max_side - height[j])
                else:
                    max_side = min(height[i], height[j])
            if j - i == 1:
                break
        return res

    def find_min(self, i, j):
        if self.mid_mat[i][j]:
            self.mid_set.add((i, j))
            # top = self.find_min(i - 1, j) if i > 0 and (i - 1, j) not in self.mid_set else float("inf")
            # bottom = self.find_min(i + 1, j) if i < self.height - 1 and (i + 1, j) not in self.mid_set else float("inf")
            # left = self.find_min(i, j - 1) if j > 0 and (i, j - 1) not in self.mid_set else float("inf")
            # right = self.find_min(i, j + 1) if j < self.length - 1 and (i, j + 1) not in self.mid_set else float("inf")
            if i > 0:
                if (i - 1, j) not in self.mid_set:
                    top = self.find_min(i - 1, j)
                else:
                    top = float("inf")
            else:
                return self.heightMap[i][j]
            if i < self.height - 1:
                if (i + 1, j) not in self.mid_set:
                    bottom = self.find_min(i + 1, j)
                else:
                    bottom = float("inf")
            else:
                return self.heightMap[i][j]
            if j > 0:
                if (i, j - 1) not in self.mid_set:
                    left = self.find_min(i, j - 1)
                else:
                    left = float("inf")
            else:
                return self.heightMap[i][j]
            if j < self.length - 1:
                if (i, j + 1) not in self.mid_set:
                    right = self.find_min(i, j + 1)
                else:
                    right = float("inf")
            else:
                return self.heightMap[i][j]
            mid = min(self.heightMap[i][j] + self.mid_mat[i][j], top, bottom, left, right)
            return max(mid, self.heightMap[i][j])
        else:
            return self.heightMap[i][j]


a = Solution()
print(a.trapRainWater([[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]]))  # 4
print(a.trapRainWater([[1]]))  # 0
print(a.trapRainWater([[19383, 10886, 12777, 16915, 17793, 18335, 15386, 10492, 16649, 11421],
                       [12362, 27, 8690, 59, 7763, 3926, 540, 3426, 9172, 5736],
                       [15211, 5368, 2567, 6429, 5782, 1530, 2862, 5123, 4067, 3135],
                       [13929, 9802, 4022, 3058, 3069, 8167, 1393, 8456, 5011, 8042],
                       [16229, 7373, 4421, 4919, 3784, 8537, 5198, 4324, 8315, 4370],
                       [16413, 3526, 6091, 8980, 9956, 1873, 6862, 9170, 6996, 7281],
                       [12305, 925, 7084, 6327, 336, 6505, 846, 1729, 1313, 5857],
                       [16124, 3895, 9582, 545, 8814, 3367, 5434, 364, 4043, 3750],
                       [11087, 6808, 7276, 7178, 5788, 3584, 5403, 2651, 2754, 2399],
                       [19932, 5060, 9676, 3368, 7739, 12, 6226, 8586, 8094, 7539]]))  # 79058
print(a.trapRainWater([[14, 20, 11, 19, 19, 16],
                       [11, 10, 7, 4, 9, 6],
                       [17, 2, 2, 6, 10, 9],
                       [15, 9, 2, 1, 4, 1],
                       [15, 5, 5, 5, 8, 7],
                       [14, 2, 8, 6, 10, 7]]))  # 11
print(a.trapRainWater([[78, 16, 94, 36],
                       [87, 93, 50, 22],
                       [63, 28, 91, 60],
                       [64, 27, 41, 27],
                       [73, 37, 12, 69],
                       [68, 30, 83, 31],
                       [63, 24, 68, 36]]))  # 44
